package com.wtgroup.demo.mianshi.算法.图;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/5 18:08
 */
public class Q_拓扑排序 {

    static class S1 {
        List<Node> doit(Graph graph) {
            // 为了不破坏原图的 in 属性, 另外用个Map存储动态的 in
            Map<Node, Integer> nodeInDegreeMap = new HashMap<>();
            Queue<Node> zeroInDegreeQueue = new LinkedList<>();
            // 找到遍历的起始点(可多个)
            for (Node node : graph.nodes.values()) {
                nodeInDegreeMap.put(node, node.in);
                if (node.in == 0) {
                    zeroInDegreeQueue.add(node);
                }
            }

            List<Node> result = new ArrayList<>();
            while (zeroInDegreeQueue.isEmpty() == false) {
                Node poll = zeroInDegreeQueue.poll();
                result.add(poll);
                if (poll.nexts != null) {
                    for (Node c : poll.nexts) {
                        // 减入度
                        nodeInDegreeMap.put(c, nodeInDegreeMap.get(c) - 1);
                        if (nodeInDegreeMap.get(c) == 0) {
                            zeroInDegreeQueue.offer(c);
                        }
                    }
                }
            }

            return result;
        }
    }

}
